#include <vector>
class Solution {
public:
	/**
	* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
	*
	* 计算01背包问题的结果
	* @param V int整型 背包的体积
	* @param n int整型 物品的个数
	* @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
	* @return int整型
	*/
	int knapsack(int V, int n, vector<vector<int> >& vw) {
		// vector<vector<int>> dp(n + 7, vector<int>(V + 7)); // 0到i最大重量，体积不超过j
		// // 不选，dp[i][j] = dp[i - 1][j]
		// 选，dp[i][j] = dp[i - 1][j - vw[i - 1][2]] + vw[i - 1][1]
		//for (int i = 1; i <= n; ++i)
		//{
		//	for (int j = 0; j <= V; ++j)
		//	{
		//		dp[i][j] = dp[i - 1][j];
		//		if (j - vw[i - 1][0] >= 0)
		//		{
		//			// cout << j << " " << vw[i - 1][0] << endl;
		//			dp[i][j] = max(dp[i][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
		//		}
		//	}
		//}
		//return dp[n][V];
		vector<int> dp(V + 7); // 滚动数组优化
		for (int i = 1; i <= n; ++i)
		{
			for (int j = V; j >= 0 && j - vw[i - 1][0] >= 0; --j)
			{
				dp[j] = max(dp[j], dp[j - vw[i - 1][0]] + vw[i - 1][1]);
			}
		}
		return dp[V];
	}
};